package Leetcode.图;

public class FloydWarshallAlgorithm {
    
    private static final int INF = -1; // 表示顶点之间不可达
    
    // 输出最短路径矩阵
    public void printSolution(int[][] dist, int V) {
        System.out.println("The following matrix shows the shortest distances between every pair of vertices");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][j] == INF)
                    System.out.print("INF ");
                else
                    System.out.print(dist[i][j] + "   ");
            }
            System.out.println();
        }
    }
    
    // 弗洛伊德算法的实现
    public void floydWarshall(int[][] graph, int V) {
        int[][] dist = new int[V][V];
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = graph[i][j];
            }
        }

        // 添加所有顶点作为中间顶点
        for (int k = 0; k < V; k++) {
            // 选择所有顶点作为源点和终点
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    // 如果i和k之间可达，且k和j之间可达，且i通过k到达j的路径比现有路径短，则更新dist[i][j]
                    if (dist[i][k] != INF && dist[k][j] != INF
                    && dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
        
        // 打印最短路径矩阵
        printSolution(dist, V);
    }
    
    public static void main (String[] args) {
        /* Let us create the following weighted graph
           10
        (0)------->(3)
        |         /|\
      5 |          |
        |          | 1
       \|/         |
        (1)------->(2)
           3           */
        int[][] graph = {
                {0, 5, INF, 10, 7, 6},
                {INF, 0, 3, INF, 2, 1},
                {INF, INF, 0, 1, 3, 4},
                {3, INF, 2, 0, 3, 4},
                {INF, INF, 2, 1, 0, 4},
                {INF, INF, INF, 2, 4, 0}
        };
        
        int V = graph.length;
        
        FloydWarshallAlgorithm fw = new FloydWarshallAlgorithm();
        
        // 调用弗洛伊德算法
        fw.floydWarshall(graph, V);
    }
}
